package preface

import "unsafe"

type MinFree struct {
	data []int
}

// 从零开始遍历，查看是否出现过
func (m *MinFree) BruteForce() int {
	i := 0
	for true {
		ok := false
		for j := 0; j < len(m.data); j++ {
			if m.data[j] == i {
				ok = true
			}
		}
		if !ok {
			return i
		}
		i++
	}
	return i
}

const (
	N           = 1000000
	WORD_LENGTH = int(unsafe.Sizeof(int(1))) * 4
)

var Bits = make([]uint32, N/WORD_LENGTH)

// set the value of the bit
func setBit(bits []uint32, i uint32) {
	bits[int(i)/WORD_LENGTH] |= 1 << (i % uint32(WORD_LENGTH))
}

// 返回bit的value
func testBit(bits []uint32, i uint32) int {
	return int(bits[int(i)/WORD_LENGTH] & (1 << (i % uint32(WORD_LENGTH))))
}

// 初始化bits
func resetBit(bits []uint32) {
	for i := 0; i < N/WORD_LENGTH; i++ {
		bits[i] = 0
	}
}

// 设置位图，标记出现过的数。再从头遍历未标记的。
func (m *MinFree) Improvement1() int {
	resetBit(Bits)
	for i := 0; i < len(m.data); i++ {
		if m.data[i] < N {
			setBit(Bits, uint32(m.data[i]))
		}
	}
	// 遍历
	for i := 0; ; i++ {
		if ^Bits[i] != 0 {
			for j := 0; ; j++ {
				if testBit(Bits, uint32(j+i*WORD_LENGTH)) == 0 {
					return i*WORD_LENGTH + j
				}
			}
		}

	}
	// return -1 means error
	// return -1
}

//  Divide and Conquer
// start 和 end 为id的范围
func Improvement2(data []int, start, end int) int {
	if len(data) == 0 {
		return start
	}
	mid := (start + end) / 2
	// 计算多少数比mid小
	count := 0
	for i := 0; i < len(data); i++ {
		if data[i] <= mid {
			data[i], data[count] = data[count], data[i]
			count++
		}
	}
	if count == mid-start+1 {
		return Improvement2(data[count:], mid+1, end)
	}
	return Improvement2(data[:count], start, mid)
}
func Improvement3(data []int, n int) int {
	l, u := 0, n-1
	// n为id可能的最大数目
	for n != 0 {
		m := (l + u) / 2
		left := 0
		for right := 0; right < len(data); right++ {
			if data[right] <= m {
				data[right], data[left] = data[left], data[right]
				left++
			}
		}
		if left == m-l+1 {
			data = data[left:]
			n = n - left
			l = m + 1
		} else {
			data = data[:left]
			n = left
			u = m
		}
	}
	return l
}
